#include <vector>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <stack>
/**
 * 详细思路
 * 1 处理边界情况
 *   - 如果链表为空或者只有一个节点 直接返回原链表 无需反转
 * 2 创建虚拟头节点dummy
 *   - 目的是统一处理left=1的情况 避免反转起点是原链表头节点时无前驱节点的问题
 *   - 将dummy的next指向原链表头节点head
 * 3 定位反转相关的关键节点
 *   - 初始化fast slow prev_node三个指针都指向dummy
 *   - 通过循环移动指针来定位
 *     - i从0开始循环到right-1
 *     - 当i小于left-1时 移动prev_node 最终prev_node停在反转区间的前驱节点（left的前一个节点）
 *     - 当i小于left时 移动slow 最终slow停在反转区间的起点节点（left节点）
 *     - 每次循环都移动fast 最终fast停在反转区间的终点节点（right节点）
 *   - 定义end节点为fast的next 即反转区间的后继节点（right的下一个节点）
 *   - 定义start节点为prev_node 即反转区间的前驱节点
 * 4 初始化反转用的三指针
 *   - prev初始化为nullptr 作为cur节点的上一个节点
 *   - cur初始化为slow 即反转区间的起点节点
 *   - next初始化为nullptr 用于保存cur的下一个节点
 * 5 执行反转核心逻辑
 *   - 循环条件为cur不等于end 即遍历完反转区间的所有节点
 *   - 每次循环中
 *     - 先用next保存cur的下一个节点 防止反转后丢失后续节点
 *     - 将cur的next指向prev 完成当前节点的反转
 *     - 将prev更新为当前的cur 作为下一个节点的上一个节点
 *     - 将cur更新为之前保存的next 继续遍历下一个节点
 * 6 连接反转后的链表各部分
 *   - 将原反转起点的next（即start->next->next）指向end 使反转区间的最后一个节点连接到后继节点
 *   - 将反转区间的前驱节点start的next指向fast（反转后的区间头节点） 完成前驱与反转区间的连接
 * 7 返回结果
 *   - 返回dummy的next 即新的链表头节点（处理了left=1的情况）
 */

using namespace std;

 struct ListNode {
      int val;
     ListNode *next;
     ListNode() : val(0), next(nullptr) {}
     ListNode(int x) : val(x), next(nullptr) {}
     ListNode(int x, ListNode *next) : val(x), next(next) {}
 };
 
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if(!head || !head->next)
            return head;
        
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        
        ListNode* fast = dummy;   
        ListNode* slow = dummy;   
        ListNode* prev_node = dummy;  
        
        int i = 0;
        while(i < right) 
        {       
            if(i < left - 1)  
                prev_node = prev_node->next;
            if(i < left)    
                slow = slow->next;
            
            fast = fast->next;  
            i++;
        }
        
        ListNode* end = fast->next;
        ListNode* start = prev_node;
        ListNode* prev = nullptr; 
        ListNode* cur = slow;     
        ListNode* next = nullptr;

        while (cur != end) {
            next = cur->next;     
            cur->next = prev;     
            prev = cur;           
            cur = next;           
        }
        
        start->next->next = end;  
        start->next = fast;      
        
        return dummy->next;
    }
};